Adj=[[1,2,3],[2],[],[]]
AdjEdgeType=[[None]*len(lst) for lst in Adj]
V=xrange(len(Adj))
color=['white']*len(Adj)
pi=[None]*len(Adj)
d=[0]*len(Adj)
f=[0]*len(Adj)
time=0

def DFS(Adj):
    for u in V:
        if color[u]=='white':
            DFS_visit(u)

def DFS_visit(u):
    global time
    color[u]='grey'
    time=time+1
    d[u]=time
    idx=-1
    for v in Adj[u]:
        idx=idx+1        
        if color[v]=='white':
            AdjEdgeType[u][idx]='Tree edge'
            pi[v]=u
            DFS_visit(v)
        elif color[v]=='grey':
            AdjEdgeType[u][idx]='Back edge'
        elif color[v]=='black':
            if d[u]<d[v]:
                AdjEdgeType[u][idx]='Forward edge'
            elif d[u]>d[v]:
                AdjEdgeType[u][idx]='Cross edge' 
    color[u]='black'
    time=time+1
    f[u]=time

if __name__=='__main__':
    print Adj
    DFS(Adj)
    print pi
    print AdjEdgeType

